package com.c2b.algorithm.leetcode.hot100;

import java.util.*;

/**
 * <a href="https://leetcode.cn/problems/group-anagrams/">字母异位词分组</a>
 * <p>给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
 * 字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。</p>
 * <pre>
 * 示例 1:
 *      输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
 *      输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
 *
 * 示例 2:
 *      输入: strs = [""]
 *      输出: [[""]]
 *
 * 示例 3:
 *      输入: strs = ["a"]
 *      输出: [["a"]]
 *
 * </pre>
 * <b>提示：</b>
 * <li>1 <= strs.length <= 10^4</li>
 * <li>0 <= strs[i].length <= 100</li>
 * <li>strs[i] 仅包含小写字母</li>
 *
 * @author c2b
 * @since 2023/4/25 10:36
 */
public class Hot049GroupAnagrams {

    public List<List<String>> groupAnagrams(String[] strs) {
        // key：将字符串排序后得到的字符串作为key，value：源子字符串集合：排序后的字符串相等的
        Map<String, List<String>> resultMap = new HashMap<>();
        for (String sourceStr : strs) {
            char[] sourceStrArr = sourceStr.toCharArray();
            Arrays.sort(sourceStrArr);
            // 排序后的字符串
            String targetStr = new String(sourceStrArr);
            List<String> strGroup = resultMap.getOrDefault(targetStr, new ArrayList<>());
            strGroup.add(sourceStr);
            resultMap.put(targetStr, strGroup);
        }
        return new ArrayList<>(resultMap.values());
    }

    public static void main(String[] args) {
        Hot049GroupAnagrams hot049GroupAnagrams = new Hot049GroupAnagrams();
        for (List<String> list : hot049GroupAnagrams.groupAnagrams(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"})) {
            for (String s : list) {
                System.out.print(s + "  ");
            }
            System.out.println();
        }
    }
}
